/**
 * 面试题 02.07. 链表相交
 * https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci/
 */
public class Solutions_mianshi_02_07 {
    public static void main(String[] args) {
//        ListNode intersectVal = new ListNode(8);
//        intersectVal.next = new ListNode(4);
//        intersectVal.next.next = new ListNode(5);

//        ListNode headA = new ListNode(4);
//        headA.next = new ListNode(1);
//        headA.next.next = intersectVal;  // {4, 1, 8, 4, 5}
//        ListNode headB = new ListNode(5);
//        headB.next = new ListNode(0);
//        headB.next.next = new ListNode(1);
//        headB.next.next.next = intersectVal;  // {5, 0, 1, 8, 4, 5}
        // output: {8} 相交节点在 8

        ListNode headA = new ListNode(2);
        headA.next = new ListNode(6);
        headA.next.next = new ListNode(4);
        ListNode headB = new ListNode(1);
        headB.next = new ListNode(5);  // output: null  没有相交节点

        ListNode result = getIntersectionNode(headA, headB);
        System.out.println(result);
    }

    /**
     * 若有相交结点，那么相交的结点一定在 headA + headB 中
     */
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode h1 = headA, h2 = headB;
        // 结束循环时：要么 h1 和 h2 是相交节点，要么都为 null
        while (h1 != h2) {
            h1 = h1 == null ? headB : h1.next;
            h2 = h2 == null ? headA : h2.next;
        }
        return h1;
    }
}
